import java.util.*;

/**
 * @author LKQ
 * @date 2022/4/10 21:40
 * @description 记忆化搜索，从删除气球变成添加气球.
 * 一开始左右两边为 1 1.方法 solve，令solve(i,j) 表示将开区间 (i,j)内的位置全部填满气球能够得到的最多硬币数
 */
public class Solution2 {
    public static void main(String[] args) {
        Solution2 solution2 = new Solution2();
        int[] nums = {9, 76, 64, 21};
        System.out.println(solution2.maxCoins(nums));
    }
    public int[][] rec;
    public int[] val;

    public int maxCoins(int[] nums) {
        int n = nums.length;
        val = new int[n + 2];
        for (int i = 1; i <= n; i++) {
            val[i] = nums[i - 1];
        }
        // 添加气球，两边都是1 1, 数组中间为实际添加的气球
        val[0] = val[n + 1] = 1;
        // 记忆化保存区间（i，j）的值，
        rec = new int[n + 2][n + 2];
        for (int i = 0; i <= n + 1; i++) {
            Arrays.fill(rec[i], -1);
        }
        return solve(0, n + 1);
    }

    public int solve(int left, int right) {
        if (left >= right - 1) {
            return 0;
        }
        if (rec[left][right] != -1) {
            return rec[left][right];
        }
        for (int i = left + 1; i < right; i++) {
            int sum = val[left] * val[i] * val[right];
            sum += solve(left, i) + solve(i, right);
            rec[left][right] = Math.max(rec[left][right], sum);
        }
        return rec[left][right];
    }

}
